/**
 * util module
 *
 * @author strlst <e11907086@student.tuwien.ac.at>
 * @date 2020-11-10
 * @brief contains auxiliary definitions and implementations of methods used to manipulate a graph structure as it is defined in "def.h"
 * @details stores a color_names array of strings that is used to output color information when debug is enabled
 */

#include "util.h"

static const char *color_names[] = { "red", "green", "blue" }; /**< stores strings associated with values in color enum for debug output purposes */

int extract_edges(struct graph *g, int optind, int argc, char **argv) {
    /* parse all remaining arguments, which are supposed to be edges */
    for (int i = optind; i < argc; i++) {
        unsigned int edge1, edge2;
        /* on wrongly formatted edges, inform user and fail */
        if (sscanf(argv[i], "%u-%u", &edge1, &edge2) < 2)
            return INVALID_INPUT;

        /* add edge */
        g->edges[g->edge_count]     = edge1;
        g->edges[g->edge_count + 1] = edge2;
        g->edge_count += 2;
    }

    /* must be a multiple of 2, otherwise an edge index is missing */
    if (g->edge_count % 2 != 0)
        return INVALID_INPUT;

    return OS_SUCCESS;
}

void init_graph(struct graph *g) {
    /* init constants */
    g->node_count = 0;
    g->edge_count = 0;
}

void print_graph(struct graph *g) {
    /* print edges */
    printf("edges: ");
    for (int i = 0; i < (g->edge_count - 2); i += 2) {
        printf(
            "%u-%u, ",
            (g->invalidated[i]     != -1) ? g->edges[i]     : 0,
            (g->invalidated[i + 1] != -1) ? g->edges[i + 1] : 0
        );
    }
    /* last edge */
    printf(
        "%u-%u\n",
        (g->invalidated[g->edge_count - 2] != -1) ? g->edges[g->edge_count - 2] : 0,
        (g->invalidated[g->edge_count - 1] != -1) ? g->edges[g->edge_count - 1] : 0
    );

    /* print nodes */
    printf("nodes: ");
    for (int i = 0; i < (g->node_count - 1); i++) {
        printf(
            "%i (colored %s), ",
            g->node_ids[i],
            color_names[g->node_colors[i]]
        );
    }
    /* last node */
    printf(
        "%i (colored %s)\n",
        g->node_ids[g->node_count - 1],
        color_names[g->node_colors[g->node_count - 1]]
    );
}

void extract_nodes(struct graph *g) {
    /* TODO: perhaps rethink O(n^2) complexity */
    /* all edges are connections between potential new nodes */
    for (int e = 0; e < (g->edge_count); e++) {
        unsigned int edge = g->edges[e];
        int skip = 0;

        /* search for pre-existing node with same id */
        for (int n = 0; n < (g->node_count); n++) {
            if ((g->node_ids[n]) == edge) {
                skip = 1;
                break;
            }
        }

        /* node was already added */
        if (skip)
            continue;

        /* initialize new node */
        g->node_ids[g->node_count] = edge;
        g->node_colors[g->node_count] = RED;
        ++g->node_count;
    }
}

void assign_random_coloring(struct graph *g) {
    /* seed time */
    srand(time(0) * getpid());

    /* go through all nodes */
    for (int i = 0; i < (g->node_count); i++) {
        /* assign random color */
        int r = rand() % 3;
        g->node_colors[i] = (enum color) r;
    }
}

void remove_edge(struct graph *g, size_t i) {
    /* assert usage */
    if (i % 2 != 0 || (i + 1) >= (g->edge_count)) {
        fprintf(stderr, "osue-3col-gen: invalid edge index specified\n");
        exit(INVALID_REMOVE_EDGE);
    }

    /* invalidate edges */
    g->invalidated[i]     = INVALID_EDGE;
    g->invalidated[i + 1] = INVALID_EDGE;
}

size_t find_invalid_edge(struct graph *g) {
    enum color color1, color2;

    /* go through all edge pairs */
    for (int e = 0; e < (g->edge_count); e += 2) {
        /* skip already invalidated edges */
        if (g->invalidated[e]     == INVALID_EDGE ||
            g->invalidated[e + 1] == INVALID_EDGE)
            continue;
        
        /* find nodes and fetch their colors */
        /* loops are implicitly targets for removal! */
        for (int n = 0; n < (g->node_count); n++) {
            if (g->node_ids[n] == g->edges[e])
                color1 = g->node_colors[n];
            if (g->node_ids[n] == g->edges[e + 1])
                color2 = g->node_colors[n];
        }

        /* if two nodes of an edge have identical colors, invalidate edge */
        if (color1 == color2)
            return e;
    }

    /* nothing found */
    return INVALID_EDGE_INDEX;
}
